#define _CRT_SECURE_NO_WARNINGS 1


//#include<string>
//#include<iostream>
//
//using namespace std;
//
//string convert(string s, int numRows)
//{
//    if (numRows == 1)
//    {
//        return s;
//    }
//    string str;
//    int size = s.size();
//    int d = 2 * numRows - 2, index = 0;
//    for (int i = 0; i < numRows; i++)
//    {
//        if (i == 0)
//        {
//            index = i;
//            while (index < size)
//            {
//                str += s[index];
//                index += d;
//            }
//        }
//        else if (i == numRows - 1)
//        {
//            index = i;
//            while (index < size)
//            {
//                str += s[index];
//                index += d;
//            }
//        }
//        else
//        {
//            index = i;
//            int index2 = d - index;
//            while (index2 < size && index < size)
//            {
//                str += s[index];
//                str += s[index2];
//                index += d;
//                index2 += d;
//            }
//            if (index < size)
//            {
//                str += s[index];
//            }
//        }
//    }
//    return str;
//}

//int main()
//{
//    string s = "PAYPALISHIRING";
//    cout << convert(s, 3) << endl;
//
//	return 0;
//}


//#include<string>
//#include<iostream>
//
//using namespace std;
//
//string Func(string s)
//{
//    string str;
//    int size = s.size(), left = 0, right = 0;
//    if (size == 1)
//    {
//        str += '1';
//        str += s[0];
//        return str;
//    }
//    while (right < size)
//    {
//        if (s[right] != s[left])
//        {
//            str += (right - left) + '0';
//            str += s[left];
//            left = right;
//        }
//        right++;
//    }
//    str += (right - left) + '0';
//    str += s[left];
//    return str;
//}
//
//string countAndSay(int n)
//{
//    string s = "1";
//    if (n == 1)
//    {
//        return s;
//    }
//    for (int i = 2; i <= n; i++)
//    {
//        s = Func(s);
//    }
//    return s;
//}
//
//int main()
//{
//    cout << countAndSay(4) << endl;
//
//	return 0;
//}


#include<vector>
#include<iostream>

using namespace std;

void sortColors(vector<int>& nums)
{
    int size = nums.size();
    int left = -1, right = size;
    int i = 0;
    while (i < right)
    {
        if (nums[i] == 0)
        {
            swap(nums[++left], nums[i++]);
        }
        else if (nums[i] == 2)
        {
            swap(nums[--right], nums[i]);
        }
        else
        {
            i++;
        }
    }
}

int main()
{
    vector<int> v = { 2,0,2,1,1,0 };
    sortColors(v);
    for (auto& e : v)
    {
        cout << e << ' ';
    }
    cout << endl;

	return 0;
}